<!DOCTYPE html>
<html>
<head>
<title>周志华《机器学习》课后习题解答系列（六）：Ch5.6 - BP算法改进</title>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<style type="text/css">
/* GitHub stylesheet for MarkdownPad (http://markdownpad.com) */
/* Author: Nicolas Hery - http://nicolashery.com */
/* Version: b13fe65ca28d2e568c6ed5d7f06581183df8f2ff */
/* Source: https://github.com/nicolahery/markdownpad-github */

/* RESET
=============================================================================*/

html, body, div, span, applet, object, iframe, h1, h2, h3, h4, h5, h6, p, blockquote, pre, a, abbr, acronym, address, big, cite, code, del, dfn, em, img, ins, kbd, q, s, samp, small, strike, strong, sub, sup, tt, var, b, u, i, center, dl, dt, dd, ol, ul, li, fieldset, form, label, legend, table, caption, tbody, tfoot, thead, tr, th, td, article, aside, canvas, details, embed, figure, figcaption, footer, header, hgroup, menu, nav, output, ruby, section, summary, time, mark, audio, video {
  margin: 0;
  padding: 0;
  border: 0;
}

/* BODY
=============================================================================*/

body {
  font-family: Helvetica, arial, freesans, clean, sans-serif;
  font-size: 14px;
  line-height: 1.6;
  color: #333;
  background-color: #fff;
  padding: 20px;
  max-width: 960px;
  margin: 0 auto;
}

body>*:first-child {
  margin-top: 0 !important;
}

body>*:last-child {
  margin-bottom: 0 !important;
}

/* BLOCKS
=============================================================================*/

p, blockquote, ul, ol, dl, table, pre {
  margin: 15px 0;
}

/* HEADERS
=============================================================================*/

h1, h2, h3, h4, h5, h6 {
  margin: 20px 0 10px;
  padding: 0;
  font-weight: bold;
  -webkit-font-smoothing: antialiased;
}

h1 tt, h1 code, h2 tt, h2 code, h3 tt, h3 code, h4 tt, h4 code, h5 tt, h5 code, h6 tt, h6 code {
  font-size: inherit;
}

h1 {
  font-size: 28px;
  color: #000;
}

h2 {
  font-size: 24px;
  border-bottom: 1px solid #ccc;
  color: #000;
}

h3 {
  font-size: 18px;
}

h4 {
  font-size: 16px;
}

h5 {
  font-size: 14px;
}

h6 {
  color: #777;
  font-size: 14px;
}

body>h2:first-child, body>h1:first-child, body>h1:first-child+h2, body>h3:first-child, body>h4:first-child, body>h5:first-child, body>h6:first-child {
  margin-top: 0;
  padding-top: 0;
}

a:first-child h1, a:first-child h2, a:first-child h3, a:first-child h4, a:first-child h5, a:first-child h6 {
  margin-top: 0;
  padding-top: 0;
}

h1+p, h2+p, h3+p, h4+p, h5+p, h6+p {
  margin-top: 10px;
}

/* LINKS
=============================================================================*/

a {
  color: #4183C4;
  text-decoration: none;
}

a:hover {
  text-decoration: underline;
}

/* LISTS
=============================================================================*/

ul, ol {
  padding-left: 30px;
}

ul li > :first-child, 
ol li > :first-child, 
ul li ul:first-of-type, 
ol li ol:first-of-type, 
ul li ol:first-of-type, 
ol li ul:first-of-type {
  margin-top: 0px;
}

ul ul, ul ol, ol ol, ol ul {
  margin-bottom: 0;
}

dl {
  padding: 0;
}

dl dt {
  font-size: 14px;
  font-weight: bold;
  font-style: italic;
  padding: 0;
  margin: 15px 0 5px;
}

dl dt:first-child {
  padding: 0;
}

dl dt>:first-child {
  margin-top: 0px;
}

dl dt>:last-child {
  margin-bottom: 0px;
}

dl dd {
  margin: 0 0 15px;
  padding: 0 15px;
}

dl dd>:first-child {
  margin-top: 0px;
}

dl dd>:last-child {
  margin-bottom: 0px;
}

/* CODE
=============================================================================*/

pre, code, tt {
  font-size: 12px;
  font-family: Consolas, "Liberation Mono", Courier, monospace;
}

code, tt {
  margin: 0 0px;
  padding: 0px 0px;
  white-space: nowrap;
  border: 1px solid #eaeaea;
  background-color: #f8f8f8;
  border-radius: 3px;
}

pre>code {
  margin: 0;
  padding: 0;
  white-space: pre;
  border: none;
  background: transparent;
}

pre {
  background-color: #f8f8f8;
  border: 1px solid #ccc;
  font-size: 13px;
  line-height: 19px;
  overflow: auto;
  padding: 6px 10px;
  border-radius: 3px;
}

pre code, pre tt {
  background-color: transparent;
  border: none;
}

kbd {
    -moz-border-bottom-colors: none;
    -moz-border-left-colors: none;
    -moz-border-right-colors: none;
    -moz-border-top-colors: none;
    background-color: #DDDDDD;
    background-image: linear-gradient(#F1F1F1, #DDDDDD);
    background-repeat: repeat-x;
    border-color: #DDDDDD #CCCCCC #CCCCCC #DDDDDD;
    border-image: none;
    border-radius: 2px 2px 2px 2px;
    border-style: solid;
    border-width: 1px;
    font-family: "Helvetica Neue",Helvetica,Arial,sans-serif;
    line-height: 10px;
    padding: 1px 4px;
}

/* QUOTES
=============================================================================*/

blockquote {
  border-left: 4px solid #DDD;
  padding: 0 15px;
  color: #777;
}

blockquote>:first-child {
  margin-top: 0px;
}

blockquote>:last-child {
  margin-bottom: 0px;
}

/* HORIZONTAL RULES
=============================================================================*/

hr {
  clear: both;
  margin: 15px 0;
  height: 0px;
  overflow: hidden;
  border: none;
  background: transparent;
  border-bottom: 4px solid #ddd;
  padding: 0;
}

/* TABLES
=============================================================================*/

table th {
  font-weight: bold;
}

table th, table td {
  border: 1px solid #ccc;
  padding: 6px 13px;
}

table tr {
  border-top: 1px solid #ccc;
  background-color: #fff;
}

table tr:nth-child(2n) {
  background-color: #f8f8f8;
}

/* IMAGES
=============================================================================*/

img {
  max-width: 100%
}
</style>
</head>
<body>
<p>相关答案和源代码托管在我的Github上：<a href="https://github.com/PY131/Machine-Learning_ZhouZhihua">PY131/Machine-Learning_ZhouZhihua</a>.</p>
<h2>5.6 BP算法改进</h2>
<blockquote>
<p><img src="Ch5/5.6.png" /></p>
</blockquote>
<p>注：本题程序基于Python实现（<a href="https://github.com/PY131/Machine-Learning_ZhouZhihua/tree/master/ch5_neural_networks/5.6_BP_improve">这里查看完整代码和数据集</a>）。</p>
<h3>1. 方法设计</h3>
<p>传统的BP算法改进主要有两类：</p>
<ul>
<li>启发式算法：如附加动量法，自适应算法。</li>
<li>数值优化算法：如共轭梯度法、牛顿迭代法、Levenberg-Marquardt法。</li>
</ul>
<p>这里我们首先采用<strong>附加动量</strong>实现基本的方法改进。然后分析算法的不足，设计面向学习率的自适应机制来改进，实现基于<strong>动态自适应学习速率</strong>的BP算法改进。</p>
<h4>(1) 附加动量项</h4>
<p>这是一种广泛用于加速梯度下降法收敛的优化方法，其<strong>核心思想</strong>是：在梯度下降搜索时，若当前梯度下降与之前梯度下降方向相同，则加速搜索，反之则减速搜索。</p>
<p>参考书p103（式5.11），标准BP算法的参数更新项为：</p>
<pre><code>∆ω(t) = ηg(t)
</code></pre>

<p>式中，∆ω(t)为第t次迭代的参数调整量，η为学习率，g(t)为第t次迭代所计算出的梯度。</p>
<p>在添加动量项之后，基于梯度下降的参数更新项为：</p>
<pre><code>∆ω(t) = η[(1-μ)g(t)+μg(t-1)]
</code></pre>

<p>始终，μ为<strong>动量因子</strong>（取值0~1）。上式也等效于：</p>
<pre><code>∆ω(t) = α∆ω(t-1)+ηg(t)
</code></pre>

<p>式中α被称为<strong>遗忘因子</strong>，α∆ω(t-1)代表之前梯度下降的方向和大小信息对当前梯度下降的调整作用。</p>
<h4>(2) 自适应学习率</h4>
<p>附加动量法面临学习率的选取的困难，进而产生收敛速度与收敛性之间的矛盾。于是另考虑引入学习速率自适应设计，这里给出一种自适应方案：</p>
<pre><code>η(t) = σ(t)η(t-1)
</code></pre>

<p>上式中，σ(t)为第t次迭代时的<strong>自适应学习速率因子</strong>，下面是其一种计算实例：</p>
<pre><code>σ(t) = 2^λ
其中λ为梯度方向：λ = sign(g(t)(t-1))
</code></pre>

<p>这样，学习率的变化可反映前面附加动量项中所说的“<strong>核心思想</strong>”。</p>
<h4>(3) 算法总结</h4>
<p>将上述两种方法结合起来，形成<strong>动态自适应学习率的BP改进算法</strong>：</p>
<p>学习算法原型可参照书p104算法图5.8，如下图所示：</p>
<p><img src="Ch5/5.6.1.png" /></p>
<p>从上图及书中内容可知，输出层与隐层的梯度项不同，故而对应<strong>不同的学习率</strong> η_1 和 η_2，算法的修改主要是第7行关于参数更新的内容：</p>
<p>将附加动量项与学习率自适应计算代入，得出公式(5.11-5.14)的调整如下图所示：</p>
<p><img src="Ch5/5.6.2.png" /></p>
<h3>2. 对比实验</h3>
<p>（<a href="https://github.com/PY131/Machine-Learning_ZhouZhihua/blob/master/ch5_neural_networks/5.6_BP_improve/BP_improve.py">点击查看完整程序</a>）</p>
<p>这里我们采用<a href="http://archive.ics.uci.edu/ml/datasets/Iris">IRIS data set</a>，实验基于python-pybrain实现，步骤如下：</p>
<pre><code>1. 搭建网络：搭建单隐层网络；
2. 训练网络：分别采用学习率固定方案和动态调整方案来实现基于BP算法的模型训练；
3. 结果比较：比较训练过程中的参数或误差收敛情况以及最终的模型预测结果；
</code></pre>

<p>BP算法实现代码可参考<a href="http://blog.csdn.net/snoopy_yuan/article/details/70765238">神经网络基础 - Python编程实现标准BP算法</a></p>
<h4>(1) 数据预分析</h4>
<p><a href="http://archive.ics.uci.edu/ml/datasets/Iris">iris（鸢尾花）数据集</a>的一些基本信息如下（参考<a href="http://archive.ics.uci.edu/ml/machine-learning-databases/iris/iris.names">iris.names</a>）：</p>
<pre><code>属性信息，4-输入（连续值），1-输出（标称值，3类）：
    Attribute Information:
       1. sepal length in cm
       2. sepal width in cm
       3. petal length in cm
       4. petal width in cm
       5. class: 
          -- Iris Setosa
          -- Iris Versicolour
          -- Iris Virginica

样本规模（150条，均匀分3类）：
    Number of Instances: 150 (50 in each of three classes)

有无缺失值（无）：
    Missing Attribute Values: None
...
</code></pre>

<p>经过相关预检，可以看出该数据集规整度很高。</p>
<p>对其中的一些变量进行可视化如下图，可以看出其类别分散特性：</p>
<p><img src="Ch5/5.6.pairplot.png" /></p>
<p>为了方便进行数值计算，采用<strong>独热编码（onehot encoding）</strong>对输出的标称数据进行数值化，这样输出由1维变为3维（每一个输出对应一类）。在最终结果处理时，可采用<strong>胜者通吃（winner-take-all）</strong>的准则选择数值最大的输出对应的类作为分类结果。</p>
<h4>(2) BP网络搭建</h4>
<p>这里搭建单隐层前馈模型，三层节点数从输入到输出依次为 &lt;4, n_h, 3&gt;，其中隐层节点数 n_h 根据实验具体进展灵活取值。</p>
<p>下面是BP网络搭建样例代码：</p>
<p><code>python
	from BP_network import *
	bpn1 = BP_network()  # initial a BP network class
	bpn1.CreateNN(4, 5, 3, actfun = 'Sigmoid', learningrate = 0.02)  # build the network</code></p>
<h4>(3) 固定学习率下的模型训练</h4>
<p>为了研究学习率对模型训练的影响，这里分别设置三个学习率：很大、很小和合适，分别得出对应训练误差曲线如下图所示：</p>
<p><img src="Ch5/5.6.lr_curve_1.png" /></p>
<p>分析上面的图，可以看出，当学习率过大时，收敛过程出现了严重的振荡，当学习率过小时，收敛过慢，当采用合适的学习率时，收敛过程稳定。</p>
<h4>(4) 自适应学习率下的模型训练</h4>
<p>根据上面关于学习率过大过小的对比实验，这里先为学习率的调整设置上下限。然后实现动态学习率下的标准BP算法。</p>
<p>最后得出固定学习率与动态学习率下训练误差收敛曲线对比如下图：</p>
<p><img src="Ch5/5.6.err_curve.png" /></p>
<p>可以看出，动态学习率的收敛速度较快，两种机制在足够多的迭代步骤后均实现了良好的精度。（另外我们看到，动态调整学习率下的收敛曲线最后阶段发生了轻微振荡，这和学习率的调整幅度（底数及遗忘系数有关系。这两个参数需要人工调试）有关）。</p>
<p>下面是最终的测试集预测误差结果：</p>
<pre><code>固定学习率：test error rate: 0.013
动态学习率：test error rate: 0.027
</code></pre>

<h3>3. 小结</h3>
<p>采用动态调整学习率的确能够大幅提升BP算法的收敛速度，在数据量很大时愈发明显。但同时也要注意学习率的取值区间和相关加速参数的设置，以期实现最优性能。</p>

</body>
</html>
<!-- This document was created with MarkdownPad, the Markdown editor for Windows (http://markdownpad.com) -->
